class Solution:
    """

threeSum 方法
检查全0数组:
if all(x == 0 for x in nums): return [[0, 0, 0]]
如果数组中所有元素都是0，直接返回 [[0, 0, 0]]。
检查0的数量:
flag = 0
if (nums.count(0) >= 3): flag = 1
如果数组中0的数量大于等于3，设置标志 flag 为1。
限制重复元素:
list2 = self.limit_duplicates(nums)
调用 limit_duplicates 方法，限制每个元素最多出现两次。
三重循环查找三元组:
list5 = []
for i in range(len(list2)):
外层循环遍历 list2。
list3 = list2[:i] + list2[i + 1:]
去掉当前元素 list2[i]，生成新的列表 list3。
for j in range(len(list3)):
中层循环遍历 list3。
list4 = list3[:j] + list3[j + 1:]
去掉当前元素 list3[j]，生成新的列表 list4。
for k in range(len(list4)):
内层循环遍历 list4。
if (list2[i] + list3[j] + list4[k] == 0):
检查当前三元组的和是否为0。
list5.append(sorted([list2[i], list3[j], list4[k]]))
如果和为0，将排序后的三元组添加到 list5 中。
去除重复的三元组:
list5 = self.remove_duplicates(list5)
调用 remove_duplicates 方法，去除 list5 中的重复三元组。
处理0的情况:
if (flag == 1): list5.append([0, 0, 0])
如果 flag 为1，表示原数组中有至少3个0，将 [0, 0, 0] 添加到 list5 中。
返回结果:
return list5
limit_duplicates 方法
统计每个元素的出现次数:
count = {}
for element in lst:
遍历列表 lst，统计每个元素的出现次数。
if element in count: count[element] += 1
如果元素已经在字典中，计数加1。
else: count[element] = 1
否则，初始化计数为1。
构建新列表:
result = []
for element, freq in count.items():
遍历字典 count，构建新列表，每个元素最多出现两次。
result.extend([element] * min(2, freq))
将元素添加到 result 中，次数为 min(2, freq)。
返回结果:
return result
remove_duplicates 方法
将每个子数组转换为元组，并放入集合中:
unique_tuples = set(tuple(sublist) for sublist in list5)
使用生成器表达式将每个子数组转换为元组，并放入集合中，集合会自动去除重复的元组。
将集合中的元组转换回列表:
unique_list = [list(tup) for tup in unique_tuples]
使用列表推导式将集合中的每个元组转换回列表。
返回结果:
return unique_list

    """
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        if  all(x == 0 for x in nums):
            return [[0,0,0]]
        flag = 0
        if (nums.count(0)>=3):
            flag=1
        list2 = self.limit_duplicates(nums)
        list5 = []
        for i in range(len(list2)):
            list3 = list2[:i] + list2[i + 1:]
            for j in range(len(list3)):
                list4 = list3[:j] + list3[j + 1:]
                for k in range(len(list4)):
                    if (list2[i] + list3[j] + list4[k] == 0):
                        list5.append(sorted([list2[i], list3[j], list4[k]]))
        list5=self.remove_duplicates(list5)
        if(flag==1):
            list5.append([0,0,0])
        return list5
    def limit_duplicates(self, lst):  # 去重
        # 创建一个字典来统计每个元素的出现次数
        count = {}
        for element in lst:
            if element in count:
                count[element] += 1
            else:
                count[element] = 1
        # 构建新的列表，每个元素最多出现两次
        result = []
        for element, freq in count.items():
            result.extend([element] * min(2, freq))
        return result
    def remove_duplicates(self,list5):
        # 将每个子数组转换为元组，并放入集合中
        unique_tuples = set(tuple(sublist) for sublist in list5)
        # 将集合中的元组转换回列表
        unique_list = [list(tup) for tup in unique_tuples]
        return unique_list


class Solution2:
    """
    这段代码定义了一个类 Solution2，其中包含一个方法 threeSum，用于找到数组中所有和为零的三个数的组合。
排序：首先对输入数组 nums 进行排序。
初始化结果列表：创建一个空列表 result 用于存储结果。
遍历数组：使用一个外层循环遍历数组，索引为 i。
跳过重复元素：如果当前元素与前一个元素相同，则跳过当前迭代。
双指针法：使用两个指针 left 和 right 分别指向当前元素的下一个位置和数组的最后一个位置。
计算总和：计算 nums[i] + nums[left] + nums[right] 的值。
判断总和：
如果总和为零，将这三个数添加到结果列表中，并跳过所有重复的 left 和 right 元素，然后移动指针。
如果总和小于零，移动左指针 left。
如果总和大于零，移动右指针 right。
返回结果：返回结果列表 result。

    """
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums.sort()  # 对数组进行排序
        result = []

        for i in range(len(nums) - 2):
            # 跳过重复的元素
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left, right = i + 1, len(nums) - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])

                    # 跳过重复的元素
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    right -= 1

        return result


lll = Solution()
print(lll.threeSum([-1, 0, 1, 2, -1, -4, 1, 1, 1, 1, 1, -2, -3, 3, 0,0,0, 4]))
